//
// Created by Administrator on 2021/7/27.
//
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

class BrowserHistory {
private:
    stack<string> backwardStack; // 储存过往浏览信息
    stack<string> forwardStack;  // 储存后续浏览信息
public:
    explicit BrowserHistory(const string &homepage) {
        backwardStack.push(homepage); // 初始化 home页面入栈
    }

    void visit(const string &url) {
        // 访问的页面入栈
        backwardStack.push(url);
        // 后续页面清空
//        while (!forwardStack.empty())
//            forwardStack.pop();
        stack<string>().swap(forwardStack);
    }

    string back(int steps) {
        for (int i = 0; i < steps and backwardStack.size() > 1; ++i) {
            forwardStack.push(backwardStack.top());
            backwardStack.pop();
        }
        return backwardStack.top();
    }

    string forward(int steps) {
        for (int i = 0; i < steps and !forwardStack.empty(); ++i) {
            backwardStack.push(forwardStack.top());
            forwardStack.pop();
        }
        return backwardStack.top();
    }
};

class BrowserHistory2 { // 用数组模拟栈
public:
    BrowserHistory2(string homepage) {
        history.push_back(homepage);
    }

    void visit(string url) {
        top = ++cur;
        if (cur == history.size())
            history.push_back(move(url));
        else history[cur] = move(url);
    }

    string back(int steps) {
        return history[cur = max(0, cur - steps)];
    }

    string forward(int steps) {
        return history[cur = min(top, cur + steps)];
    }

private:
    vector <string> history;
    int top = 0, cur = 0;
};


int main() {
    auto *browserHistory = new BrowserHistory("leetcode.com");
    browserHistory->visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
    browserHistory->visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
    browserHistory->visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
    cout << browserHistory->back(1)
         << endl;                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
    cout << browserHistory->back(1)
         << endl;                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
    cout << browserHistory->forward(1)
         << endl;                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
    browserHistory->visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
    cout << browserHistory->forward(2) << endl;                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
    cout << browserHistory->back(
            2)
         << endl;                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
    cout << browserHistory->back(7)
         << endl;                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"
    delete browserHistory;
    return 0;
}